510. Toasts
You are going to
toast some slices of bread for an upcoming party. You have a frying pan that
can hold at most k toasts at the same time. Toasting one side
of a toast takes 2 minutes.
Assume that
placing a toast on the pan, flipping it, and removing it are instantaneous
operations.
Write a program
that determines the minimum number of minutes required to toast n slices
of bread. Each toast must be toasted on both sides. A toast cannot be removed
from the pan before or after the exact 2 minutes needed to toast one
side.
Input. Two
integers n and k (0 ≤ n ≤
1000, 1 ≤ k ≤ 50) – the number of
toasts and the capacity of the pan (in toasts).
Output. Print the
minimum number of minutes required to toast all n slices.
|
Sample
input |
Sample
output |
|
3 2 |
6 |
SOLUTION
mathematics
Algorithm analysis
If n = 0, the answer is 0.
If the number of toasts n does not exceed the pan’s capacity k (n ≤ k), then toasting all the
toasts on both sides will take 4 minutes.
Since each toast must be toasted on both sides, a total of 
toasting rounds is required. Each
toasting round (placing up to k toasts on the pan at the same time)
takes 2 minutes.
Therefore, if n > k, the minimum time
required to toast all the toasts is 2 * minutes.
Example
Suppose there
are n = 3 toasts, and the pan can hold k = 2 toasts at a time.
Let us label the sides of the toasts as 1a, 1b, 2a, 2b,
3a, 3b.
Then all 6 sides
can be toasted in 6 minutes as follows:
· First toasting:
1a and 2a – 2 minutes;
· Second toasting:
1b and 3a – 2 minutes;
· Third toasting:
2b and 3b – 2 minutes;
Total: 3
toasting rounds of 2 minutes each, which makes 6 minutes.
Algorithm implementation
Read the input data.
scanf("%d %d",&n,&k);
If n = 0, the answer is 0.
if (!n) res = 0; else
If the number of toasts does not exceed the capacity of the pan, it will
take 4 minutes to toast them.
if (n <= k) res = 4; else
{
Each toast must be toasted on both sides, which means that the total
number of sides to toast is 
. Each toasting session (regardless of the number of toasts
on the pan, as long as it does not exceed its capacity) takes 2 minutes.
res = 2 * n / k;
if (2 * n %
k) res++;
res *= 2;
}
Print the answer.
printf("%d\n",res);
Java implementation
import java.util.*;
public class Main
{
public static void main(String []args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
int k = con.nextInt();
int res;
if (n == 0) res = 0; else
if (n <= k) res = 4; else
{
res = 2 * n / k;
if (2 * n % k > 0) res++;
res *= 2;
}
System.out.println(res);
con.close();
}
}